Robust Subspace Recovery (RSR) aims to identify an underlying d-dimensional subspace from a dataset heavily corrupted by outliers. Complexity-theoretic results establish a threshold for the problem's computational hardness based on the dimensionscaled signal-to-noise ratio (DS-SNR): the problem is SSE-hard when the DS-SNR is strictly less than 1, and solvable via practical algorithms when it is greater than 1 under general position assumptions. However, the exact behavior of practical algorithms at the critical boundary DS-SNR = 1 has remained unknown. Specifically, we prove that TME converges exactly to the true subspace for DS-SNR 1 under a new stability condition, which is less restrictive than the general position assumptions used in prior literature. I. Introduction Robust Subspace Recovery (RSR) is a fundamental problem in robust statistics, machine learning, and computer vision. The primary goal of RSR is to identify an underlying low-dimensional linear subspace from a dataset that is heavily corrupted by outliers. The standard formulation of the noiseless RSR problem assumes a dataset X = {xi}Ni=1 RD consisting of n1 inliers lying exactly on a d-dimensional linear subspace L RD, and n0 outliers lying strictly off L . We refer to such a dataset as a noiseless inlier-outlier dataset, where the total number of points is N = n0 +n1. The central algorithmic question in noiseless RSR is under what conditions one can exactly and efficiently recover the underlying d-subspace L . A natural metric for characterizing the difficulty of this problem is the ratio of inliers to outliers, n1/n0, which can be viewed as a signal-to-noise ratio (SNR) [8], [11], [12]. This leads to the dimension-scaled SNR (DS-SNR), denoted by δS: δS:= n1/d n0/(D d) . Hardt and Moitra [5] established a fundamental lower bound, showing that when δS < 1, the noiseless RSR problem is Small Set Expansion (SSE)-hard, a property conjectured to be equivalent to NP-hardness [15]. In the special case of hyperplanes (d = D 1), they showed NP-hardness by invoking a result from [7]. The noiseless RSR problem is SSE-hard if δS < 1.

We thank the authors for their careful reading and helpful comments. They also noted the scalability concerns. On very large networks, the precision of MIP-solvers may also become an issue. R#1: "The only thing I feel is missing, is a discussion on how to verify if a network is in general position, and We will discuss this in the paper. R#2: Experimental questions/suggestions and "...are there any other properties of networks that could be in-33 We will present a more complete version of Table 1 in future iterations.

Weaknesses: 1. Except for section 3, other theoretical findings/results seem rather standard. For example, the reformulation techniques involved in section 5 have been widely used in mixed-integer programs and even for certifying the adversarial robustness, e.g., SMT solver, nothing new. Also, theorem 1 can be easily obtained via several simple inductions. ReLU network is subdifferential regular under the general position assumption? See Theorem 49 in [1] for details.

We consider the natural problem of learning a ReLU network from queries, which was recently remotivated by model extraction attacks. In this work, we present a polynomial-time algorithm that can learn a depth-two ReLU network from queries under mild general position assumptions. We also present a polynomial-time algorithm that, under mild general position assumptions, can learn a rich class of depth-three ReLU networks from queries. For instance, it can learn most networks where the number of first layer neurons is smaller than the dimension and the number of second layer neurons. These two results substantially improve state-of-the-art: Until our work, polynomial-time algorithms were only shown to learn from queries depth-two networks under the assumption that either the underlying distribution is Gaussian (Chen et al. (2021)) or that the weights matrix rows are linearly independent (Milli et al. (2019)). For depth three or more, there were no known poly-time results. With the growth of neural-network-based applications, many commercial companies offer machine learning services, allowing public use of trained networks as a black-box. Those networks allow the user to query the model and, in some cases, return the exact output of the network to allow the users to reason about the model's output.